Section: New Results

Collaborative distributed consensus algorithms for control and estimation

Distributed Control

Participants : A. Seuret [Contact person] , C. Canudas de Wit, L. Briñón Arranz, G. Rodrigues de Campos, K. H. Johansson [KTH] .

The first contribution in this area deals with the source-seeking problem in which the task is to locate the source of some signal using a fleet of autonomous underwater vehicles. The objective is here to use the underwater vehicles equipped with appropriate sensors as a mobile sensors network. In [28] and [29] , we present a method which allows estimating the gradient of the signal propagation using a distributed consensus filters [27] . To do so, we consider a group of vehicles uniformly distributed in a fixed circular formation. We then show that this distributed consensus algorithm converges to good approximation of the gradient of the signal propagation. The algorithm takes into account the communication constraints and depends on direct signal measurements. Our approach is based on the previous results in formation control to stabilize the fleet to elastic formations which can be time-varying [29] and in a collaborative source-seeking algorithm proposed earlier by members of the team. The results are supported through computer simulations.

The second contribution on collaborative control concerns the design and analysis of a distributed algorithm whose goal is symmetric robot deployment. This activity results from the collaboration between INRIA and KTH provided by the visit of G. Rodrigues de Campos (PhD student) at KTH during six month. The objective is here to propose a hierarchical control strategy composed of two stages. The first one corresponds to an algorithm for swarm dispersion and a second concerns the design of a additional algorithm which minimizes the inter-agent angles. In this context, the behavior of each vehicle depends only on the relative positions of agents it can sense. The article submitted to ICRA'12 [84] , presents some simulation examples for different configuration support the derived theoretical results.

Distributed Estimation

• Collaborative protocols for estimation and control

  Participants : A. Kibangou [Contact person] , A. L. F. Almeida [Universidade Federal do Ceara] .

  In wireless communication systems, spatial diversity plays a key role in combating signal fading arising from multipath propagation. As long as the transmitter is equipped with multiple antennas, it is well known that spatial diversity can be exploited further at the transmitter by means of space-time coding [88] . In contrast to conventional (single-user) space-time coding/decoding, when dealing with cooperative wireless networks, spatial diversity must resort to distributed space-time coding/decoding, where a collection of distributed antennas belonging to multiple terminals work in a coordinated way to encode/decode the transmitted information [85] .

  For this purpose, we have extended the Khatri-Rao Space time coding method proposed in [86] to cooperative networks (see Fig. 5 ). For cooperating nodes having a single antenna, these nodes constitute a virtual antenna array at both transmitting and receiving front-end. At each node, the received data can be viewed as slices of a third-order tensor. Therefore, retrieving the informative data is achieved by means of a CP tensor decomposition using an Alternating Least Squares (ALS) algorithm for example. When all the slices cannot be gathered at the same node, for storage resources limitations for example, a distributed ALS method can be used as in [77] , which is an average consensus based method. In a consensus problem, a group of network nodes try to reach agreement on a given quantity of interest that depends on their local values [79] . Instead of using a standard consensus method where convergence is achieved asymptotically, we have proposed a finite time average consensus approach that relies on the knowledge of the graph topology. The proposed algorithm and its performance evaluation by means of simulations are described in [37] .

• Kalman filtering based distributed fault detection and isolation

  Participants : A. Kibangou [Contact person] , F. Garin, S. Hachour, A. Esna Ashari.

  This year, we have started a research activity related to distributed fault detection and isolation. Our first work has been the master thesis of S. Hachour on the monitoring of a solar farm. Indeed, stimulated by increasing energy demand and ecological concerns, clean energy production with renewable resources is a key research topic that presents a largely unexplored potential of development.

  For this purpose, solar farms constitute power plants of the future. In such systems, electricity is produced thanks to the combined action of a large number of interconnected modules (solar panels). Each module individually produces energy, but only their interconnection allows reaching the global task of a relevant energy production. Due to the interconnection topology, a local fault on a given module can induce damageable effects on the whole network. In order to detect and localize a fault, a sensor network can be deployed over the farm. Thanks to the recent advances in wireless communications, the sensors can be equipped with wireless devices, creating a network of communicating sensors. A classical way to exploit such a network would be to create a hierarchical (tree-like) structure which conveys all measurements to a centralized computer which would analyze all data. However, a failure in a communication link or in the centralized computer would result in breakdown of the whole fault detection system, which is an unacceptable risk in an application domain of strategic importance such as a power plant. Therefore we have proposed a decentralized approach that relies on local data aggregation using the computing and communicating resources of the sensor nodes. As a consequence, nodes cooperation produces a global decision, available at each point of the network, and computable even in the case where a few sensors or links are unavailable. The monitoring procedure is achieved in a distributed way using a Kalman filtering approach. Now, by considering the sensor network as the system of interest, we try to derive distributed estimation methods that are robust to malicious entities and monitoring methods to detect anomalies in the system due to these malicious entities or malfunctioning of the network. These issues are addressed by A. Esna Ashari during his post-doctoral stay in our team.

Figure 5. Cooperative communication system.

Distributed Consensus

• Finite-time distributed average consensus on sensor networks

  Participant : A. Kibangou [Contact person] .

  Nowadays, several distributed estimation algorithms are based on the average consensus concept. Average consensus can be reached using a linear iterations scheme where each node repeatedly updates its value as a weighted linear combination of its own value and those of its neighbors. The main benefit of using a linear iterations scheme is that, at each time-step, each node only has to transmit a single value to each of its neighbors. Based on such a scheme, several algorithms have been proposed in the literature. However, in the majority of the proposed algorithms the weights are chosen so that all the nodes asymptotically converge to the same value. Sometimes, consensus can be embedded as a step of more sophisticated distributed algorithm as it is the case for the Distributed Kalman filter [80] and the Distributed Alternating Least Squares algorithm [77] . Obviously, asymptotic convergence is not suitable for these kinds of distributed methods. Even though, speed convergence of consensus algorithm have been explored in [78] and [91] with the goal to derive fast consensus algorithms, running standard consensus in finite-time constitute a source of errors not easily quantifiable. Sometimes, bounds can be derived. Therefore, it is interesting to address the question of exact consensus in finite-time.

  For time-invariant network topologies and in the perfect information exchange case, i.e. without channel noise nor quantization, we have shown that the finite-time average consensus problem can be solved as a matrix factorization problem with joint diagonalizable matrices depending on the Graph Laplacian eigenvalues [38] , [48] . Moreover, the number of iterations is equal to the number of distinct nonzero eigenvalues of the graph Laplacian matrix. Then, by periodically restarting the consensus algorithm, we have also shown that, in the noisy case, exact average consensus can be achieved asymptotically.

• Quadratic indices for performance evaluation of consensus algorithms

  Participants : F. Garin [Contact person] , S. Zampieri [Università di Padova] , E. Lovisari [Università di Padova] .

  Traditional analysis of linear average-consensus algorithms studies, for a given communication graph, the convergence rate, given by the essential spectral radius of the transition matrix (i.e., the second largest eigenvalues’ modulus). For many graph families, such analysis predicts a performance which degrades when the number of agents grows, basically because spreading information across a larger graph requires a longer time. However, when considering other well-known quadratic performance indices (involving all the eigenvalues of the transition matrix), the scaling law with respect to the number of agents can be different. This is consistent with the fact that, in many applications, for example in estimation problems, it is natural to expect that a larger number of cooperating agents has a positive, not a negative effect on performance. It is natural to use a different performance measure when the algorithm is used for different purposes, e.g., within a distributed estimation or control algorithm. Examples of various relevant costs can be found in the book chapter [50] and in the references therein.

  We are interested in evaluating the effect of the topology of the communication graph on performance, in particular for large-scale graphs. Motivated by the study of wireless sensor networks, our main objective is to understand the limitations which arise when agents are limited to truly local interactions, i.e., the neighborhoods are determined by being `near' in a geometric (Euclidean) way, differently from graphs with few but possibly `distant' connections, such as in small world models. At first [18] we consider graphs which are regular lattices (infinite lattices, or grids on tori, or grids on hyper-cubes), which are examples of geometrically local interactions, but also have a very rich structure: their symmetries allow to exploit powerful algebraic tools, such as the discrete Fourier transform over rings, to compute their eigenvalues, and then find bounds on the associated costs. Then, we extend the results to a more general class of graphs, thus showing that the behavior of lattices is mainly due to the local nature of interactions and not to the symmetries. To do so, we exploit the analogy between reversible Markov chains and resistive electrical networks. This latter work is part of the Ph.D. thesis of E. Lovisari at University of Padova, Italy.

• Distributed averaging over digital noisy networks

  Participants : F. Garin [Contact person] , R. Carli [Università di Padova] , G. Como [MIT] , P. Frasca [Politecnico di Torino] .

  We study iterative distributed averaging algorithms for networks whose nodes can communicate through memoryless erasure broadcast channels. In order to compare the performance of different algorithms, we define suitable complexity measures, which account for the number of channel transmissions (communication complexity), and, respectively, of in-node computations (computational complexity) required to achieve a desired precision. These performance measures are particularly relevant, as they allow for directly estimating the energy consumption of such distributed computation systems, as well as their time-complexity.

  The algorithms we propose combine the classical iterative linear consensus algorithm (where at each iteration, each agent receives the states of its neighbors and takes a suitable convex combination of them), with source-channel coding schemes for the reliable transmission of real numbers on noisy channels. Our algorithms involve a sequence of transmission phases, of increasing duration, in which the agents attempt to broadcast their state, i.e. their current estimate of the global average, to their neighbors, alternated to averaging steps, in which the agents' states are updated. These algorithms are fully distributed, and they do not require the agents to have any global knowledge of the network structure or size. Our main result shows that such algorithms drive the agents to state agreement (consensus) which can be made arbitrarily close to the true average. The number of channel transmissions and in-node computations is shown to grow at most poly-logarithmically in the desired precision. We also show how communication feedback, when available, allows one to modify the algorithms, achieving asymptotic average consensus (i.e., state agreement on the average of the initial observations), and reducing the computational and communication complexities. This work is presented in the paper [15] . In the paper [22] , we present and analyze a modified algorithm, which can be used when source coding (compression) and channel coding (error correction) are performed by two separate encoders. Such algorithm takes into the account the fact that, even without any channel feedback, the part of the error which is due to lossy compression and not to channel noise is perfectly known by the transmitter, and a compensation can be introduced, thus improving performance.

• Distributed Consensus algorithms

  Participant : A. Seuret [Contact person] .

  Concerning this problem, we address the classical issues of the stability analysis of consensus algorithm in continuous-time. The objective of the present work is to show that the performances classical consensus algorithms can be improved using an appropriate memory of the controlled state. We want to design a novel type of consensus algorithm which uses not only the current state of the algorithm but also a sampled version of it. The key problems are here the design of the best parameters, i.e., the sampling period and the ratio between the contributions of the current and the sampled states. It has to be noticed that a usual intuition is to say that using past values of the state a reduction of performances or to instability. However, our contributions show that this is not always in single and double integrator consensus algorithms [41] . These contributions is based on an LMI framework and based on algebraic communication matrix structure. The efficiency of the method is tested for different network communication schemes.

Distributed real-time Simulation of numerical models

Participants : D. Simon [Contact person] , A. Ben Khaled [IFPEN] , M. Ben Gaid [IFPEN] .

To allow real-time simulation of high fidelity engine models, different techniques have to be applied in order to fulfill the real-time constraints. Real-time simulation involves trade-offs between several aspects, such as real-time constraints, models computational complexity and integration accuracy. Traditionally HIL designers consider that every step of the simulation must be real-time and deterministic, leading to strongly synchronized systems, at the cost of ineffective computation burdens. It has been shown that adequately splitting the plant's model into weakly synchronized sub-systems allows for efficiently using variable steps numerical integrators, simulation speed-ups and subsequent effective parallel versions of HIL systems [25] .